package leetcodehot100;

public class _4寻找两个正序数组的中位数 {

    //2.二分查找
    /**
     *  1. A[k/2 -1] < B[k/2 -1]  ===> A[0] 到 A[k/2 -1] 排除
     *  2. A[k/2 -1] > B[k/2 -1]  ===> B[0] 到 B[k/2 -1] 排除
     *  3. A[k/2 -1] == B[k/2 -1]  ===> 归入第一种情况
     *  k = (n + m ) /2
     *  k / 2
     *  特殊情况
     *      1. 一个数组为空 , 直接返回另一个数组中第 k 小的元素
     *      2. k=1，只要返回两个数组首元素的最小值即可
     *      3. A[k/2 -1] 或 B[k/2 -1] 越界，可以选取对应数组中的最后一个元素。
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length , len2 = nums2.length;
        int len = len1 + len2;
        if(len % 2 ==1){
            int mid = len / 2;
            double median = getKthElement(nums1,nums2,mid+1);
            return  median;
        }else{
            int mid1 = len/2 -1 , mid2 = len / 2;
            double median = getKthElement(nums1,nums2,mid1+1) + getKthElement(nums1,nums2,mid2+1);
            return median / 2.0 ;
        }
    }
    int getKthElement(int[] nums1, int[] nums2, int k) {
        int len1 = nums1.length , len2 = nums2.length;
        int index1 = 0 , index2 = 0;
        int kElement = 0;
        while (true){
            if(index1==len1)
                return nums2[index2+k-1];
            if(index2==len2)
                return nums1[index1+k-1];
            if(k==1)
                return Math.min(nums1[index1],nums2[index2]);

            int half = k/2;
            int newIndex1 = Math.min(index1+half,len1) - 1;
            int newIndex2 = Math.min(index2+half,len2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if(pivot1<=pivot2){
                k -= (newIndex1-index1+1);
                index1 = newIndex1 + 1;
            }else{
                k -= (newIndex2-index2 +1);
                index2 = newIndex2 + 1;
            }
        }
    }

    //1.简单粗暴，先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] nums = new int[m + n];
        if (m == 0) {
            if (n % 2 == 0) {
                return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
            } else {

                return nums2[n / 2];
            }
        }
        if (n == 0) {
            if (m % 2 == 0) {
                return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
            } else {
                return nums1[m / 2];
            }
        }

        int count= 0;
        int i = 0 , j =0;
        while (count!=(m+n)){
            if (i == m) {
                while (j != n) {
                    nums[count++] = nums2[j++];
                }
                break;
            }
            if (j == n) {
                while (i != m) {
                    nums[count++] = nums1[i++];
                }
                break;
            }

            if (nums1[i] < nums2[j]) {
                nums[count++] = nums1[i++];
            } else {
                nums[count++] = nums2[j++];
            }

        }
        if (count % 2 == 0) {
            return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
        } else {
            return nums[count / 2];
        }

    }
}
